/**
 * 迭代树节点，必须包含 children 属性，表示包含的子节点
 */
export type RecursionTree<T> = T & {
  children?: RecursionTree<T>[];
};

/**
 * 判断是否为子节点的
 */
export type IsChildFunction<T> = (parentNode: T, childNode: T) => boolean;

/**
 * 父子节点关系类型
 */
export type IsChildConfig = {
  // 节点 key
  parentKey: string;
  // 子节点 key
  key: string;
};

/** 将 flat 数组变成 tree 型结构
 * @param arr
 * @param isChild 判断是否是子节点的方法
 * @param customizer 生成节点时，是否对节点字段进行加工处理，直接生成目标节点结构
 */
export function array2tree<
  NodeValue extends { [key: string]: any },
  CustomizerReturn,
  ReadonlyNodeValue extends Readonly<NodeValue>,
>(
  arr: ReadonlyNodeValue[],
  isChild: IsChildFunction<ReadonlyNodeValue> | IsChildConfig,
  customizer?: (node: ReadonlyNodeValue) => CustomizerReturn,
) {
  const root = {} as ReadonlyNodeValue;

  const innerIsChildFunc: IsChildFunction<ReadonlyNodeValue> =
    typeof isChild === "function"
      ? isChild
      : (pNode, node) => {
          if (!pNode[isChild.key] && !node[isChild.parentKey]) return true;
          return pNode[isChild.key] === node[isChild.parentKey];
        };

  const innerCustomizer = (node: ReadonlyNodeValue) =>
    customizer ? customizer(node) : node;

  const validateSelf = (node: ReadonlyNodeValue) =>
    innerIsChildFunc(node, node);

  const pushedFlag: Array<boolean> = [];

  const func = (
    parent: ReadonlyNodeValue,
    isRoot: boolean = true,
  ): RecursionTree<CustomizerReturn | NodeValue> => {
    const node = [];
    for (let i = 0; i < arr.length; i++) {
      if (!isRoot && validateSelf(parent)) break;
      if (pushedFlag[i]) continue;
      const item = arr[i];
      if (innerIsChildFunc(parent, item)) {
        pushedFlag[i] = true;
        const child = func(item, false);
        node.push(child);
      }
    }
    return {
      ...innerCustomizer(parent),
      children: node.length > 0 ? node : undefined,
    };
  };
  const result = func(root);
  return result.children || [];
}
